
#ifndef AFTERMATH_ALGEBRA_PERMUTATION_HPP_INCLUDED
#define AFTERMATH_ALGEBRA_PERMUTATION_HPP_INCLUDED

#include <algorithm>
#include <cstdint>
#include <functional>
#include <iostream>
#include <stdexcept>
#include <tuple>
#include <vector>

namespace aftermath
{
    namespace algebra
    {
        class permutation;

        /// <summary>
        /// An iterator for <see cref="permutation" />.
        /// </summary>
        class permutation_iterator
        {
            const permutation* m_permutation_pointer;
            std::size_t m_position;

        public:
            permutation_iterator(const permutation* p_permutation, std::size_t position)
                : m_permutation_pointer(p_permutation), m_position(position)
            {
            }

            // These three methods form the basis of an iterator for use with
            // a range-based for loop.
            bool operator !=(const permutation_iterator& other) const
            {
                return this->m_position != other.m_position;
            }

            // This method must be defined after the definition of <see cref="permutation_iterator" />
            // since it needs to use it.
            std::size_t operator *() const;

            permutation_iterator& operator ++()
            {
                ++(this->m_position);
                // Although not strictly necessary for a range-based for loop
                // following the normal convention of returning a value from
                // operator++ is a good idea.
                return *this;
            }
        };

        class permutation
        {
            std::vector<std::size_t> m_indices = {};

        public:
            permutation() = default;

            explicit permutation(std::size_t size)
            {
                this->m_indices.reserve(size);
                for (std::size_t i = 0; i < size; i++) this->m_indices.push_back(i);
            }

            template <typename t_source_type>
            explicit permutation(const std::vector<t_source_type>& source) : permutation(source.size())
            {
                this->order_by(source);
            }

            template <typename t_source_type>
            void order_by(const std::vector<t_source_type>& source)
            {
                this->order_by(source, std::less<t_source_type>());
            }

            // Remark: <source> is intentionally passed as a copy.
            template <typename t_source_type, typename t_predicate_type>
            void order_by(std::vector<t_source_type> source, t_predicate_type comparer = std::less<t_source_type>())
            {
                std::sort(this->m_indices.begin(), this->m_indices.end(), [&source, &comparer](std::size_t i, std::size_t j){
                    return comparer(source[i], source[j]);
                });
            }

            // Remark: <source> is intentionally passed as a copy.
            template <typename t_source_type, typename t_selector_type, typename t_predicate_type>
            void order_by(std::vector<t_source_type> source, t_selector_type selector, t_predicate_type comparer)
            {
                //typedef decltype(selector(source[0])) dest_type;
                std::sort(this->m_indices.begin(), this->m_indices.end(), [&source, &selector, &comparer](std::size_t i, std::size_t j){
                    return comparer(selector(source[i]), selector(source[j]));
                });
            }

            // Applies the permutation to a vector.
            template <typename t_data_type>
            std::vector<std::reference_wrapper<t_data_type>> ref(std::vector<t_data_type>& source) const
            {
                if (source.size() != this->m_indices.size()) throw std::out_of_range("<source> has to be of the same size as the permutation.");

                std::vector<std::reference_wrapper<t_data_type>> permuted = {};
                permuted.reserve(source.size());
                for (std::size_t i = 0; i < source.size(); i++) permuted.emplace_back(std::ref(source[this->m_indices[i]]));

                return permuted;
            }

            // Applies the permutation to a vector.
            template <typename t_data_type>
            std::vector<std::reference_wrapper<const t_data_type>> cref(const std::vector<t_data_type>& source) const
            {
                if (source.size() != this->m_indices.size()) throw std::out_of_range("<source> has to be of the same size as the permutation.");

                std::vector<std::reference_wrapper<const t_data_type>> permuted = {};
                permuted.reserve(source.size());
                for (std::size_t i = 0; i < source.size(); i++) permuted.emplace_back(std::cref(source[this->m_indices[i]]));

                return permuted;
            }

            std::size_t size() const 
            {
                return this->m_indices.size(); 
            }

            std::size_t operator [](std::size_t index) const
            {
                return this->m_indices[index];
            }

            permutation_iterator begin() const
            {
                return permutation_iterator(this, 0U);
            }

            permutation_iterator end() const
            {
                return permutation_iterator(this, this->size());
            }

            friend std::ostream& operator <<(std::ostream& os, const permutation& that)
            {
                bool is_first = true;
                for (std::size_t index : that.m_indices)
                {
                    if (is_first) is_first = false;
                    else os << ",";
                    os << index;
                }
                return os;
            }
        };

        std::size_t permutation_iterator::operator *() const
        {
            return this->m_permutation_pointer->operator [](this->m_position);
        }
    }
}

#endif // AFTERMATH_ALGEBRA_PERMUTATION_HPP_INCLUDED
